package com.ztom.v2;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Deque;

/**
 * @author ZhangTao
 */
public class Code14MergeIntervals {

    public static void main(String[] args) {

        int[][] ints = new int[][]{
                new int[]{1, 3},
                new int[]{2, 6},
                new int[]{8, 10},
                new int[]{15, 18},
        };
        System.out.println(Arrays.deepToString(merge(ints)));
    }

    public static int[][] merge(int[][] intervals) {
        Deque<int[]> res = new ArrayDeque<>(intervals.length);

//        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));

        for (int i = 0; i < intervals.length; i++) {
            // 第一个区间直接先放入
            if (i == 0) {
                res.addLast(intervals[0]);
                continue;
            }
            // 前一个区间
            int[] pre = res.peekLast();
            // 当前区间
            int cl = intervals[i][0];
            int cr = intervals[i][1];

            if (pre[1] < cl) {
                // 无法合并
                res.add(intervals[i]);
            } else {
                // 合并区间: lr 可能在第二区间, 也可能包含第二区间
                // 直接更新前一个区间的右边界
                pre[1] = Math.max(pre[1], cr);
            }
        }
        return res.toArray(new int[0][]);
    }
}
